package leetcode.dp;

/**
 一条包含字母A-Z 的消息通过以下映射进行了 编码 ：

 'A' -> "1"
 'B' -> "2"
 ...
 'Z' -> "26"
 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

 "AAJF" ，将消息分组为 (1 1 10 6)
 "KJF" ，将消息分组为 (11 10 6)
 注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

 题目数据保证答案肯定是一个 32 位 的整数。
 */
public class NumDecodings91 {

    public int numDecodings(String s) {
        char[] chars = s.toCharArray();

        //dp[i] 表示以s的第i（索引）个字符结尾，有多少种解码方式。
        int []dp = new int[chars.length];

        if(s.charAt(0)=='0')
            return 0;

        if(s.length()==1)
            return 1;

        //判断第2个数
        if(s.charAt(1)=='0' && !isValide(s,1))
            return 0;

        dp[0]=1;
        dp[1] = (isValide(s,1)&&s.charAt(1)!='0')?2:1;

        for (int i = 2; i < s.length(); i++) {

            if(s.charAt(i)=='0' && !isValide(s,i))
                return 0;

            if(isValide(s,i)){//可以和前面一个数字组成
                if(s.charAt(i)!='0'){//dp[i-1]：不融合  dp[i-2]：融合使用
                    dp[i] = dp[i-1]+dp[i-2];
                }
                else//当前数字位0，必须和前面融合
                    dp[i] = dp[i-2];
            }
            else//不可以和前面一个数字组成
                dp[i] = dp[i-1];
        }

        return dp[s.length()-1];
    }

    private boolean isValide(String s,int i){
        String numStr = s.substring(i - 1, i + 1);
        int num = Integer.parseInt(numStr);
        return num >= 10 && num <= 26;
    }

    public static void main(String[] args) {
        String str  = "301";
        int i = new NumDecodings91().numDecodings(str);
        System.out.println(i);
    }
}